/* 
 * CMPS 258: Programming Languages
 *        Assignment 2 - Part2: "Spy" - March 24, 2008
 *        Group name: Doomsday
 *        Authors:  Ramsey Nasser (ID# 200600496) 
 *                  Hadi Abu Rislan (ID# 200600426) 
 *                  Kevin Azzam (ID# 200602033)
 * 
 * Main program.
 * 
 * This file includes two assignment-specific functions: a function to load
 * the test cases, and the implementation of our spy-trapping algorithm.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "graph.h"

int errexit(const char *format, ...);

/*
 * Load test cases from a file.
 * 
 * The file is assumed to be in the format outlined in the assignment. The
 * function generates a graph for each test case and copies them in to the
 * array cases. The number of test cases is copied into cases_num.
 */
void load_test_cases(char* filename, graph** cases, int* cases_num) {
	char buf[32];
	graph* g;
	unsigned int R, T, x, y, i, linenum=0;
	
	// Load the file
	FILE* graph_file = fopen(filename,"r");
	if(!graph_file)
		errexit("Error opening file '%s",filename);
	
	*cases_num = 0;
	// Loop until a 0 0 line is found
	while(TRUE) {
		// Parse the first line, get number of rooms and tunnels, die on error
		fgets(buf,32,graph_file);
		sscanf(buf,"%d %d",&R, &T);
		linenum++;
		if(R > 50) errexit("Error in %s@%d : Too many rooms",filename,linenum);
		if(T > 1000) errexit("Error in %s@%d : Too many tunnels!",filename,linenum);
		if(R == 0 && T == 0) break;
		// Take "room 0" into consideration
		R++;
		
		// Create a graph with R verts
		g = graph_init(GRAPH_UNDIRECTED);
		graph_add_verts(g,R);
		
		// Loop through T lines, create edges in the graph
		for(i=0;i<T;i++) {
			fgets(buf,32,graph_file);
			sscanf(buf,"%d %d",&x, &y);
			linenum++;
			if(x > R || y > R) errexit("Error in %s@%d : Undefined room!",filename,linenum);
			graph_connect_verts(g,x,y);
		}
		
		// Point to new graph
		cases[*cases_num] = g;
		*cases_num += 1;
	}
}

/*
 * Trap a spy in an underground base.
 * 
 * Given an underground base (represented by the graph g), and the fact that
 * the spy starts in room 1, this function determines which edges need to be
 * broken in order to trap the spy.
 * 
 * The edges to break are copied into edges_to_break, and the number of edges is
 * copied into edges num.
 */
void seal_in_spy(graph* g, edge* edges_to_break, int* edges_num) {
	int i,j;
	path* paths[10];
	int path_num=0;
	edge* step_to_break;
	
	// Get every path from 1 to 0
	graph_get_all_paths(g,1,0,paths,&path_num,NULL);
	
	// Increment the frequency of each step in each path
	for(i=0;i<path_num;i++)
		for(j=0;j<paths[i]->size;j++)
			paths[i]->steps[j]->freq++;
	
	*edges_num = 0;
	// Break most frequent steps in each path
	for(i=0;i<path_num;i++) {
		if(!path_is_broken(paths[i])) {
			step_to_break = path_get_most_frequent_step(paths[i]);
			step_to_break->broken = TRUE;
			edges_to_break[*edges_num] = *step_to_break;
			*edges_num += 1;
		}
	}
}

/*
 * Display usage message
 */
void usage() {
	printf("Usage: spy TESTCASESFILE\n");
	exit(1);
}

int main(int argc, char** argv) {
	graph* test_cases[32];
	edge collapsed_edges[32];
	int i, j, cases_num, collapsed_edges_count;
	
	if(argc != 2)
		usage();
	
	load_test_cases(argv[1],test_cases,&cases_num);
	
	// For each test case, determine what edges need to be collapsed
	for(i=0;i<cases_num;i++) {
		seal_in_spy(test_cases[i],collapsed_edges,&collapsed_edges_count);
		printf("Case %d: %d\n",i+1,collapsed_edges_count);
		printf("Tunnel(s) to destroy:\n");
		for(j=0;j<collapsed_edges_count;j++)
			printf("    %d <-> %d\n",collapsed_edges[j].from->id,collapsed_edges[j].to->id);
		printf("\n");
	}
	return 0;
}
